🏔️ 최대 힙으로 K번째 큰 수 찾기

배열에서 K번째로 큰 값을 전체 정렬 없이 효율적으로 구하는 문제입니다.

1️⃣ 문제 접근

• 전체를 정렬하면 O(n log n)이지만, K가 작다면 굳이 전체를 정렬할 필요 없음
• 크기 K인 **최소 힙(Min-Heap)**을 유지하면서, 힙 크기가 K를 넘으면 가장 작은 값을 제거
• 모든 값을 순회한 뒤 힙의 루트(최솟값)가 바로 K번째로 큰 값

2️⃣ 풀이 코드 (배열 기반 간단 구현)

function findKthLargest(nums, k) {
  const heap = [];

  for (const num of nums) {
    heap.push(num);
    heap.sort((a, b) => a - b); // 간단화를 위해 정렬 사용 (실제로는 힙 구현 권장)
    if (heap.length > k) heap.shift();
  }

  return heap[0];
}

findKthLargest([3, 2, 1, 5, 6, 4], 2); // 5

⚠️ 실제 서비스 코드에서는 매번 정렬하는 대신 진짜 힙 자료구조를 사용해야 O(n log k)의 이점을 살릴 수 있음

✍️ 한 줄 정리

K번째 큰 수는 크기 K짜리 최소 힙을 유지하며 작은 값을 계속 걸러내는 방식으로, 전체 정렬 없이 O(n log k)에 구할 수 있다.